1. Field
It is related to an error correction device and a descramble circuit.
2. Description of the Related Art
Storage media, such as optical discs, have memory capacities that have been increasing over recent years. Accordingly, the time taken to read data from such large-capacity storage media must be shortened. However, flaws on an optical disc generated during manufacture and smears on the surface of the optical disc may make it difficult to correctly read data at high speeds from such an optical disc. To prevent problems associated with erroneous data, the optical disc system stores Reed-Solomon error correcting codes together with data. An error correction device performs error correction based on the error correcting codes and restores the original correct data. However, the processing time required by such error correction is long. To shorten the time taken to read data, error correction must be performed at higher speeds.
New high-density optical discs developed recently feature long-duration storage of video data with high picture quality and audio data with high sound quality. One example of such high-density optical discs is a Blu-ray Disc (BD). For example, Japanese Laid-Open Patent Publication No. 2003-242720 describes a method for storing data in a high-density optical disc. An error detecting code (EDC) and an error correcting code (ECC) are appended to data stored in a BD. The EDC is used to detect an error in the data when the data is read. The ECC is used to correct the detected error.
The format of data that is stored in a BD will now be described in detail. As shown in FIG. 1, user data UD includes 32 data frames DF0 to DF31 (collectively referred to as “data frames DF”). A single data frame DF includes 2048 bytes (2 kilobytes) of user data and an EDC consisting of 4 bytes. The 4-byte EDC follows the 2048-byte user data. The EDC is calculated using the equation shown below.
                                          E            ⁢                                                  ⁢            D            ⁢                                                  ⁢                          C              ⁡                              (                x                )                                              =                                                    ∑                                  i                  =                  31                                0                            ⁢                                                b                  i                                ⁢                                  x                  i                                                      =                                          I                ⁡                                  (                  x                  )                                            ⁢              mod              ⁢                                                          ⁢                              G                ⁡                                  (                  x                  )                                                                    ⁢                                  ⁢                  where          ,                                          ⁢                                    I              ⁡                              (                x                )                                      =                                          ∑                                  i                  =                  16415                                32                            ⁢                                                b                  i                                ⁢                                  x                  i                                                              ,                                    G              ⁡                              (                x                )                                      =                                          x                32                            +                              x                31                            +                              x                4                            +              1                                                          Equation        ⁢                                  ⁢        1            
The user data is scrambled by DF unit before preserved in ED. Through the scrambling process, the user data UD is converted to a scramble data frame SDF, which consists of 2052 rows of 32 columns of data elements d(u, v) as shown in FIG. 3A. The data frames DF of the scramble data frame SDF are arranged in columns. In the data elements d(u, v), u indicates the row number of each data element of the scramble data frame SDF and v indicates the column number of each data element of the scramble data frame SDF.
As known in the art, the scramble data is generated by performing an exclusive OR operation on each byte of the original data, which is a data frame that has not yet been scrambled, and the lower eight bits of a scramble value SC. The scramble value SC is generated by a scrambling-value generation circuit 100 shown in FIG. 2. As shown in FIG. 2, the generation circuit 100 uses a predetermined generation polynomial Φ(x) (Φ(x)=x16+x15+x13+x4+1 in the example of FIG. 2). The generation circuit 100 includes a feedback shift register 101 and EOR circuits 102, 103, and 104. The feedback shift register 101 includes bits b15 to b0.
The EOR circuit 102 outputs a calculation result of the exclusive OR operation performed on the bit b15 and the bit b14 to the EOR circuit 103. The EOR circuit 103 outputs a calculation result of the exclusive OR operation performed on the calculation result output from the EOR circuit 102 and the bit b12 to the EOR circuit 104. The EOR circuit 104 outputs a calculation result of the exclusive OR operation performed on the calculation result output from the EOR circuit 103 and the bit b3 to the bit b0.
The shift register 101 reads an initial value S0 of the scramble value, and outputs the lower eight bits (bits b7 to b0) of the initial value S0 to an EOR circuit (not shown) to which the original data is provided. The EOR circuit scrambles the data element D0 of each data frame, or the first byte of each data frame by performing an exclusive OR operation on the lower eight bits of the scramble value SC (initial value S0) and the data element D0. Through the scrambling process, the EOR circuit scrambles the data element D0 to generate a scramble data element sD0. The scramble data element sD0 is written using the equation shown below. In the equations used in this specification and the equations written in the drawings attached to the specification, ^ denotes an exclusive OR operation.sD0=D0^S0  Equation 2
The same initial value S0 is used to scramble all data frames DF0 to DF31 of one set of user data UD.
In response to the pulses of a clock signal CLK, the shift register 101 shifts the values of the bits b14 to b0 respectively to bits b15 to b1, and reads an output of the EOR circuit 104 as the value of the bit b0. After the eighth pulse of the clock signal CLK, that is, after the bits are shifted by eight bits (one byte), the generation circuit 100 outputs the values of the bits b7 to b0 to the EOR circuit (not shown) to which the original data is provided. The scramble value SC in this state is written as S0*γ1, where S0 is the initial value of the scramble value SC and γ is a 1-byte shift operator that is defined by the generation polynomial Φ(x). More specifically, S0*γ1 indicates the scramble value SC that is obtained by shifting the bits of the initial value S0 by one byte in accordance with the generation polynomial Φ(x). The data element D1 of each data frame, which is the second byte of each data frame, is scrambled by performing an exclusive OR operation on of the lower eight bits of the scramble value SC (=S0*γ1) and the data element D1. Through the scrambling process, the data element D1 is scrambled to generate a scramble data element sD1 using the equation shown below.sD1=D1^S0·γ1  Equation 3
The scramble data elements sD2 to sD2051 are generated in the same manner using the equation shown below.sD2=D2^S0·γ2 sD3=D3^S0·γ3 sD2051=D2051^S0·γ2051  Equation 4
In the equation, S0*γ3 indicates the scramble value SC that is obtained by shifting the bits of the initial value S0 by three bytes in accordance with the generation polynomial Φ(x). In the equation, S0*γ2051 indicates the scramble value SC that is obtained by shifting the bits of the initial value S0 by 2051 bytes in accordance with the generation polynomial Φ(x).
The generated scramble data elements sD0 to sD2051 of each data frame DF are arranged serially from above in the column direction. This generates the scramble data frame SDF described above.
As shown in FIGS. 3A and 3B, the scramble data frame SDF (refer to FIG. 3A) is converted to a data block DB, which consists of 216 rows of 304 columns of data elements (refer to FIG. 3B). In detail, in the scramble data frame SDF, data elements d(u, v) of each single data frame DF arranged in the column direction are stored into the data block DB in the order indicated using arrows drawn using solid lines in FIG. 3B. More specifically, the data elements d(0, 0) to d(215, 0) of the data frame DF0 are stored serially from above into the first column of the data block DB. The data elements d(216, 0) to d(431, 0) of the data frame DF0 are stored serially from above into the second column of the data block DB. The data elements d(1944, 0) to d(2051, 0) of the data frame DF0 are stored serially from above into the first to 108th rows of the tenth column of the data block DB. Next, the data elements d(0, 1) to d(107, 1) of the data frame DF1 are stored serially from above at positions adjacent to the position of the last data element d(2051, 0) of the data frame DF0, or specifically into the 109th to 216th rows of the tenth column of the data frame DF0. The data elements d(108, 1) to d(323, 1) of the data frame DF1 are stored serially from above into the eleventh column of the data block DB. The data elements d(1836, 1) to d(2051, 1) of the data frame DF1 are stored serially from above into the nineteenth column of the data block DB. The data elements of the data frames DF2 to DF31 are stored into the data block DB in the same manner as the data elements of the data frames DF0 and DF1. In this manner, the data elements d(u, v) of all the data frames DF are stored into the data block DB. As a result, when the even number data frames (for example, the data frames DF0, DF2, and DF4) and the odd number data frames (for example, the data frames DF1, DF3, and DF5) are counted all together, the data block DB includes two data frames DF each of which consists of 216 rows of 19 columns of data elements d(u, v). The 216 rows of 19 columns of data elements d(u, v) of each data frame are arranged in a two-dimensional manner in the data block DB. In other words, the single data block DB includes scramble data frames SDF each of which is arranged after every two data frames DF.
As shown in FIG. 4, an ECC unit LDCp (in other words, an ECC parity) is appended to the data block DB, which consists of 216 rows of 304 columns of data elements d(u, v) as described above. The ECC parity includes 32 rows of 304 columns of parity bits p(i, j). In detail, 32-byte parity bits p(i, j) are appended to each column of the data block DB. This forms a parity-appended block PB (“long-distance code” (LDC) block), which consists of 216 rows of 304 columns of data elements e(i, j) and 32 rows of 304 columns of parity bits p(i, j). In the data elements e(i, j) and the parity bits p(i, j), i indicates the row number of each data element of the parity-appended block PB and j indicates the column number of each data element of the parity-appended block PB. The parity bit p is calculated using the equation shown below.
                                          p            ⁡                          (              x              )                                =                                    x              8                        +                          x              4                        +                          x              3                        +                          x              2                        +            1                          ⁢                                  ⁢                  α          =          00000010                ⁢                                  ⁢                              g            ⁡                          (              x              )                                =                                    ∏                              i                =                0                            31                        ⁢                                                  ⁢                          (                              x                -                                  α                  i                                            )                                                          Equation        ⁢                                  ⁢        5            
The ECC unit LDCp is an error correcting code that is used to correct errors occurring in data elements of the parity-appended block PB arranged in the column direction. The ECC unit LDCp is used to generate an LDC syndrome (parity calculation result), which is used to perform error correction of the parity-appended block PB in the column direction.
The parity-appended block PB, which consists of 248 rows of 304 columns of data elements, is converted to an LCD cluster LDCc, which consists of 496 (=248*2) rows of 152 (=304/2 columns of data elements (hereafter referred to as a “cluster LDCc”, which is shown in FIG. 6).
In detail, through a first interleaving process, the data elements e(i, j) and the parity bits p(i, j) are first interleaved at positions f(m, n) in the block shown in FIG. 5 based on a predetermined rule. In the positions f(m, n), m indicates the row number of each data element of the cluster LDCc and n indicates the column number of each data element of the cluster LDCc.
The first interleaving process will now be described in detail with reference to FIGS. 4 and 5. In the first interleaving process, the data elements e(i, j) and the parity bits p(i, j) in the even-numbered columns, that is, the data elements e(i, j) and the parity bits p(i, j) in which j=0, 2, 4, 6, 8, . . . , 302 (even-numbered columns), are interleaved at positions f(m, n)=f(2i, j/2). Also, the data elements e(i, j) and the parity bits p(i, j) in the odd-numbered columns, that is, the data elements e(i, j) and the parity bits p(i, j) in which j=1, 3, 5, 7, 9, . . . , 303 (odd-numbered columns), are interleaved at positions f(m, n)=f(2i+1, (j−1)/2). For example, the data element e(1, 2) of an even-numbered column is arranged at the position f(2, 1) because m=2*1=2 and n=2/2=1. The data element e(1, 3) of an odd-numbered column is arranged at the position f(3, 1) because m=2*1+1=3 and n=(3−1)/2=1. The first interleaving process generates the data block shown in FIG. 5, which consists of 496 rows of 152 columns of data elements.
The data (the data elements e and the parity bits p) shown in FIG. 5, which has been subjected to the first interleaving process, is then subjected to a second interleaving process. The second interleaving process generates the cluster LDCc shown in FIG. 6.
The second interleaving process will now be described in detail. In the second interleaving process, the data elements e(i, j) and the parity bits p(i, j) arranged at the positions f(m, n) are shifted to the left within the same row by the number of bytes corresponding to a shift amount SI written using the equation shown below.SI=mod(div(m,2)*3,152)  Equation 6
In this equation, mod(a, b) is a function to return the remainder resulting from division of a by b, whereas div(a, b) is a function to return an integer that is smaller by one than the quotient of the division of a by b.
Based on the shift amount SI, the data elements e(i, j) and the parity bits p(i, j) arranged at the positions f(m, n1), at which n=n1, are interleaved at the positions f(m, n2), at which n=n2=n1−SI. The direction in which the data element and the parity bit are shifted is changed cyclically. When n2 is a negative value, the column number n of the position to which the data element and the parity bit are actually shifted is set as one of serial numbers from 151 descending as the absolute value of n2 increases. More specifically, the column number n is set in a manner that n2=−1 corresponds to n=151 and n2=−2 corresponds to n=150.
For example, at the positions f at which m=2 and 3, the shift amount of each data element e is written as SI=mod(1*3, 152)=3. In this case, the data elements e are all shifted by three bytes to the left within the same row. More specifically, the data element e(1, 0) arranged at the position f(2, 0) and the data element e(1, 1) arranged at the position f(3, 0) in FIG. 5 are interleaved at the position f(2, 149) and the position f(3, 149), at which the column number n=149 corresponding to n2=0−3=−3. In the same manner, the data elements e arranged at the positions f at which m=2 and 3 are all shifted to the left by three bytes within the same row.
The parity-appended block PB is subjected to the first and second interleaving processes in this manner. This generates the cluster LDCc shown in FIG. 6.
A burst indicator subcode (BIS) cluster BISc (hereafter referred to as a “cluster BISc”), which consists of 496 rows of three columns of data elements, is then interleaved in the cluster LDCc described above as shown in FIGS. 7A and 7B. The cluster BISc includes a data block consisting of 720 bytes and a parity consisting of 768 bytes. The 720-byte data block includes address information and user control data. As shown in FIG. 7B, the cluster BISc is divided by every column (1 byte). One of the resulting divisional parts of the cluster BISc (B1 to B3 in FIG. 7A) is inserted every after 38 columns (38 bytes) of the cluster LDCc.
An ECC cluster ECCc (hereafter referred to as a “cluster ECCc”, which is shown in FIG. 7B) consists of the cluster LDCc and the cluster BISc. The cluster ECCc is modulated through, for example, 17PP modulation before written to the BD. This format of data stored in the BD enables detection and correction of an error to be performed in a highly reliable manner when the data is read from the BD.
The operation of reading data stored in the BD will now be described. As shown in FIG. 8, a controller 110 inputs and outputs data to and from the BD, which serves as a storage medium. In the controller 110, a demodulation circuit 111 first reads data from the BD. The demodulation circuit 111 demodulates the read data to generate a cluster ECCs, and stores the cluster ECCs into a buffer memory 120. An LDC syndrome generation circuit 112 reads a cluster LDCc included in the cluster ECCc stored in the buffer memory 120, and changes the arrangement order of data elements of the cluster LDCc to the original order of the data elements prior to the first and second interleaving processes. More specifically, the LCD syndrome generation circuit 112 reads the cluster LDCc as the parity-appended block PB (refer to FIG. 4) before the first and second interleaving processes, while performing the first and second interleaving processes. The LDC syndrome generation circuit 112 then generates an LDC syndrome (syndrome calculation result) based on the parity-appended block PB, and provides the LDC syndrome to the error correction circuit 114.
The BIS syndrome generation circuit 113 reads the cluster BISc that is included in the cluster ECCc, which is stored in the buffer memory 120. The BIS syndrome generation circuit 113 then generates a BIS syndrome based on the cluster BISc, and provides the BIS syndrome to the error correction circuit 114. The error correction circuit 114 then corrects an error in the user data UD included in the cluster ECCs based on the LDC syndrome and the BIS syndrome.
The descramble circuit 115 reads, from the buffer memory 120, the data elements e corresponding to the user data UD of the cluster LDCc that has been subjected to the error correction, while subjecting the data elements e to the first and second interleaving processes. More specifically, the descramble circuit 115 reads, as the data block DB that has been subjected to the error correction, the data elements e that have been subjected to the error correction from the buffer memory 120 (refer to FIG. 3B). The descramble circuit 115 then descrambles the data block DE by subjecting each data frame DF of the data block DB to the descrambling process. In detail, the descramble circuit 115 generates the same scramble value SC as the scramble value SC used when the data has been scrambled. The descramble circuit 115 performs an exclusive OR operation on the lower eight bits of the scramble value SC and each byte of the data frame DF to generate descramble data elements dD0 to dD2051 using the equation shown below.dD0=sD2^S0dD1=sD1^S0·γ1 dD2051=sD2051^S0·γ2051  Equation 7
An EDC checking circuit 116 transfers the descramble data block DB (including the user data UD) to an external device, such as a host computer, via an interface circuit 117. The EDC checking circuit 116 checks error detecting codes (EDC) based on the descramble data block DB. In this EDC checking, the EDC checking circuit 116 generates an EDC syndrome EDCS for every 2052-byte data frame DF. In detail, the descramble data elements dD0, dD1, dD2, . . . , dD2049, dD2050, and dD2051 are transferred from the descramble circuit 115 and input to the EDC checking circuit 116 in the stated order as shown in FIG. 9. The degree of the weighting vector that is used to weight each 2052-byte descramble data element dDU is written using the polynomial expression (input polynomial) below.I(X)=X2051+X2050+X2049+ . . . +X2+X1+X0  Equation 8
The EDC calculation is the process of weighting each term of the above input polynomial using a vector β. Thus, the EDC syndrome EDCS is calculated using the equation shown below.EDCS=β2051·X2051^β2050·X2050^β2049·X2049^ . . . ^β2·X2^β1·X1^X0  Equation 9
More specifically, the EDC syndrome EDCS is generated by weighting every 1-byte data element using the first-degree vector β1 when the 1-byte data element (for example, each of the descramble data elements dD0 and dD2050) is calculated. Thus, the degree of the vector β by which the data element is weighted is higher as the data element is input at an earlier timing. The degree of the vector β by which the data element is weighted is lower as the data element is input at a later timing. For example, the vector β corresponding to the data element dD0, which is input at the earliest timing, has the highest degree of 2051 (β2051). The vector β corresponding to the data element dD2051, which is input at the latest timing, has the lowest degree of 0 (β0=1). When the 1-byte data element Xn is weighted using the vector β1, the data element Xn that is weighted is shifted by one byte in accordance with a predetermined generation polynomial G(x) (G(x)=x32+x31+x4+1 in this example). The EDC checking circuit 116 determines that the error correction has been completed successfully when all the calculated EDC syndromes indicate zero. The EDC checking is completed based on this determination.
In recent years, host computers process data at a higher speed. Thus, storage devices are required to read and write data at a higher speed. However, the storage devices, which have a limited capacity to access buffer memory 120, does not increase data reading speed any further. More specifically, the conventional controller 110 involves accesses (1) to (5) of the buffer memory 120 described below, and therefore does not increase the access speed any further. As a result, the controller 110 fails to perform the error correction at any higher speed.
(1) The demodulation circuit 110 accesses the buffer memory 120 to store a cluster ECCc.
(2) The LDC syndrome generation circuit 112 accesses the buffer memory 120 to read a cluster LDCc.
(3) The BIS syndrome generation circuit 113 accesses the buffer memory 120 to read a cluster BISc.
(4) The error correction circuit 114 accesses the buffer memory 120 to subject the cluster LDCc to error correction.
(5) The descramble circuit 115 accesses the buffer memory 120 to read the cluster LDCc after the error correction.
Moreover, the LDC syndrome generation circuit 112 is required to perform first and second de-interleaving processes when reading the clusters LDCc from the buffer memory 120 as the parity-appended block PB. In the same manner, the descramble circuit 115 is also required to perform first and second de-interleaving processes when reading the data elements e of the cluster LDCc from the buffer memory 120 as the data block DB. When the buffer memory 120 is an external buffer memory, the buffer memory is typically formed by a synchronous dynamic random access memory (SDRAM), which is inexpensive and has a low processing speed. Thus, when the clusters LDCc are read while the arrangement order of the clusters LDCc is being changed, the parity-appended block PB (or the data block DB) is read from the buffer memory 120 as small pieces of data. In other words, the amount of data obtained per access to the buffer memory 120 is small in this case. This would lower the access efficiency of the buffer memory 120, and decrease the access bandwidth of the buffer memory 120.
FIG. 10 shows a controller 130 that decreases the required amount of access to the buffer memory 120. The controller 130 temporarily stores a single cluster ECCs in its internal memory 131. The controller 130 includes an LDC syndrome generation circuit 112 and a BIS syndrome generation circuit 113 that directly access the internal memory 131. In other words, the LDC syndrome generation circuit 112 and the BIS syndrome generation circuit 113 do not access the buffer memory 120. This structure reduces the entire required amount of access to the buffer memory 120, and enables error correction to be performed at a higher speed as compared with the structure shown in FIG. 8.
However, the structure shown in FIG. 10 has a further problem. To perform the error correction in the manner described above, an error correcting circuit 114 may need to have data in units of clusters ECCc. Thus, the internal memory 131 of the controller 130 shown in FIG. 10 may need to be formed by a large-capacity buffer memory that may store data of a single ECC cluster. This would increase the circuit scale of the controller 130.